package hot;

import java.util.HashMap;
import java.util.Map;

public class Num337 {
    Map<TreeNode,Integer> map1 = new HashMap<>();
    Map<TreeNode,Integer> map2 = new HashMap<>();
    public int rob(TreeNode root) {
        dfs(root);
        return Math.max(map1.getOrDefault(root,0),map2.getOrDefault(root,0));
    }
    public void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.left);
        dfs(root.right);
        map1.put(root,root.val +map2.getOrDefault(root.left,0) +map2.getOrDefault(root.right,0));
        map2.put(root,Math.max(map1.getOrDefault(root.left,0),map2.getOrDefault(root.left,0)) +Math.max(map1.getOrDefault(root.right,0),map2.getOrDefault(root.right,0)));
    }
}
